
import numpy as np
import matplotlib.pyplot as plt
import itertools
import math


def calculate_copeland(node, nodes, edges, directions):
    copeland_score = 0
    for node2 in nodes:
        if node == node2:
            continue
        if node2 > node:
            if directions[edges[(node, node2)]] == "0":
                copeland_score += 1
        elif directions[edges[(node2, node)]] == "1":
            copeland_score += 1
    return copeland_score


def calculate_max_copeland(nodes, edges, directions):
    return max(calculate_copeland(node, nodes, edges, directions) for node in nodes)


def run_se(nodes, edges, directions):
    """Returns Copeland score of winner on the seeding given by nodes
    Edges give indices into directions, and directions is a string consisting of 0s and 1s
    (0 indicates that the first item in the pair wins)
    """
    orig_nodes = nodes
    
    # Run SE
    while len(nodes) > 1:
        next_level = []
        for i in range(0, len(nodes), 2):
            if i + 1 == len(nodes):
                next_level.append(nodes[i])
            else:
                u, v = nodes[i], nodes[i + 1]
                if u > v:
                    u, v = v, u
                if directions[edges[(u, v)]] == "0":
                    next_level.append(u)
                else:
                    next_level.append(v)
        nodes = next_level
    
    return calculate_copeland(nodes[0], orig_nodes, edges, directions)


def simulate_all(n):
    """Returns an np array E[d+(F(T))]/(max_{s in S} d+(s)) for every tournament, T, on n nodes
    """
    nodes = list(range(n))
    edges = {}
    num_edges = 0
    for i in range(len(nodes)):
        for j in range(i + 1, len(nodes)):
            u = nodes[i]
            v = nodes[j]
            edges[(u, v)] = num_edges
            num_edges += 1
    
    res = []
    format_string = f"{{:0{num_edges}b}}"
    for tournament in range(2 ** num_edges):
        directions = format_string.format(tournament)
        num_seedings = 0
        total = 0
        for seeding in itertools.permutations(nodes):
            total += run_se(seeding, edges, directions)
            num_seedings += 1
        expected_winner_score = total / num_seedings
        max_copeland_score = calculate_max_copeland(nodes, edges, directions)
        res.append(expected_winner_score / max_copeland_score)
    return np.array(res)


def theoretical_min(n):
    return math.log2(n) / (n - 2)


def simulate_visual(num_nodes):
    the_min = theoretical_min(num_nodes)
    responses = simulate_all(num_nodes)
    fig, ax = plt.subplots()
    ax.plot(np.sort(responses))
    ax.hlines([the_min, np.mean(responses)], 0, len(responses) - 1, color="red")
    ax.set_title(f"$n = {num_nodes}$")
    print(the_min, np.mean(responses))
    plt.show()


simulate_visual(5)

0.7739760316291208 0.9036458333333335


simulate_visual(6)

0.646240625180289 0.9285481770833334


import random
def simulate_sample_both(n, n_tournaments, n_seedings):
    """Returns an np array E[d+(F(T))]/(max_{s in S} d+(s)) for n_tournaments tournaments, T, on n nodes
    with n_seedings per tournament
    """
    np.random.seed(0)
    random.seed(0)
    
    nodes = list(range(n))
    edges = {}
    num_edges = 0
    for i in range(len(nodes)):
        for j in range(i + 1, len(nodes)):
            u = nodes[i]
            v = nodes[j]
            edges[(u, v)] = num_edges
            num_edges += 1
    
    res = []
    for tournament in range(n_tournaments):
        directions = "".join(random.choices("01", k=num_edges))
        num_seedings = 0
        total = 0
        for seeding in range(n_seedings):
            total += run_se(np.random.permutation(nodes), edges, directions)
            num_seedings += 1
        expected_winner_score = total / num_seedings
        max_copeland_score = calculate_max_copeland(nodes, edges, directions)
        res.append(expected_winner_score / max_copeland_score)
    return np.array(res)

def simulate_visual_sample_both(num_nodes, n_tournaments, n_seedings):
    the_min = theoretical_min(num_nodes)
    responses = simulate_sample_both(num_nodes, n_tournaments, n_seedings)
    fig, ax = plt.subplots()
    ax.plot(np.sort(responses))
    ax.hlines([the_min, np.mean(responses)], 0, len(responses) - 1, color="red")
    ax.set_title(f"$n = {num_nodes}$")
    print(the_min, np.min(responses), np.mean(responses))
    plt.show()


for i in range(5, 200):
    simulate_visual_sample_both(i, 2000, 100)

0.7739760316291208 0.7000000000000001 0.9024350000000001

0.646240625180289 0.7775 0.9257958333333334

0.5614709844115209 0.79 0.91982825

0.5 0.778 0.9123719166666667

0.45284642877747316 0.715 0.8470238333333334

0.4152410118609203 0.7542857142857143 0.8720693214285714

0.3843812909596997 0.7525 0.8730926488095238

0.3584962500721156 0.75875 0.8768149503968254

0.3364036107400993 0.7544444444444445 0.8651854437229438

0.3172795768381337 0.755 0.8695323358585858